package problem.year2021.january;

import java.math.BigInteger;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

/**
 * 2021年1月14日
 * 给定由若干 0 和 1 组成的数组 A。我们定义 N_i：从 A[0] 到 A[i] 的第 i 个子数组被解释为一个二进制数（从最高有效位到最低有效位）。
 * 返回布尔值列表 answer，只有当 N_i 可以被 5 整除时，答案 answer[i] 为 true，否则为 false。
 * 示例 1：
 * <p>
 * 输入：[0,1,1]
 * 输出：[true,false,false]
 * 解释：
 * 输入数字为 0, 01, 011；也就是十进制中的 0, 1, 3 。只有第一个数可以被 5 整除，因此 answer[0] 为真。
 * <p>
 * 示例 2：
 * <p>
 * 输入：[1,1,1]
 * 输出：[false,false,false]
 * <p>
 * 示例 3：
 * <p>
 * 输入：[0,1,1,1,1,1]
 * 输出：[true,false,false,false,true,false]
 * <p>
 * 示例 4：
 * <p>
 * 输入：[1,1,1,0,1]
 * 输出：[false,false,false,false,false]
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/binary-prefix-divisible-by-5
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class January14 {

    public List<Boolean> prefixesDivBy5(int[] A) {
        List<Boolean> list = new ArrayList<Boolean>();
        int prefix = 0;
        int length = A.length;
        for (int i = 0; i < length; i++) {
            prefix = ((prefix << 1) + A[i]) % 5;
            list.add(prefix == 0);
        }
        return list;
    }

    /**
     * 存在内存溢出问题
     * @param A
     * @return
     */
    public List<Boolean> copy1(int[] A) {
        int len = A.length;
        List<Boolean> list = new LinkedList<Boolean>();
        long t = 0;// t 表示当前list[n]所代表的十进制
        for (int i = 0; i < len; i++) {
            t = (A[i] + t * 2)%5;
            System.out.println(t + "======" + i);
            list.add(t == 0);
        }
        return list;
    }

    /**
     * 存在内存使用过大问题
     * @param A
     * @return
     */
    public List<Boolean> copy2(int[] A) {
        int len = A.length;
        List<Boolean> list = new LinkedList<Boolean>();
        BigInteger p = BigInteger.valueOf(0);// p 表示上一位list[n-1]所代表的二进制
        BigInteger t = BigInteger.valueOf(0);// t 表示当前list[n]所代表的二进制
        for (int i = 0; i < len; i++) {
            if (A[i] == 0){
                t = p.multiply(BigInteger.valueOf(2));
            } else {
                t = p.multiply(BigInteger.valueOf(2)).add(BigInteger.valueOf(1));
            }
//            t = A[i] == 0 ? p * 2 : p * 2 + 1;
//            System.out.println(t + "======" + i);
//            list.add(t % 5 == 0);
            BigInteger k = t.remainder(BigInteger.valueOf(5));
            boolean b = k.equals(BigInteger.valueOf(0));
            list.add(b);
            p = t;
        }
        return list;
    }

    public static void main(String[] args) {
        int[] list = new int[]{1, 0, 1, 1, 1, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 1, 1, 1, 1, 1, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 1, 1, 1, 1, 1, 1, 0, 1, 1, 0, 1, 0, 0, 0, 0, 0, 0, 1, 0, 1, 1, 1, 0, 0, 1, 0};
        List<Boolean> list1 = new January14().copy1(list);
        list1.forEach(System.out::println);
    }
}
